package com.study02.liangshuxiangjia;

import java.util.ArrayList;

/**
 * Created by wwl on 2022/2/21 21:43
 */
public class TwoNumAdd {
    //解题主方法
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;         //标记头尾，头部最后用来输出，尾部用来连接其他节点
        int carry = 0;                             //进位标志，初始位0
        while (l1 != null || l2 != null) {         //两个节点中，只有还有节点不为空就继续
            int x = l1 != null ? l1.val : 0;       //因为while循环中，是||的判断，存在为空的情况，l1不为空的话x取l1的val值，为空x就取0
            int y = l2 != null ? l2.val : 0;       //同上
            int addNum = x + y + carry;            //计算相同位数节点的和（带有地位的进位标志）
            carry = addNum / 10;                   //取进位标志

            if (head == null) {                    //第一次head为空
                tail = head = new ListNode(addNum % 10);
            } else {
                tail.next = new ListNode(addNum % 10); //之后用tail来添加新节点
                tail = tail.next;
            }

            if (l1 != null)                         //如果l1不为空，就取l1的下一个节点
                l1 = l1.next;
            if (l2 != null)                         //同上
                l2 = l2.next;
        }

        if (carry == 1) {                           //while循环结束后，判断是否最高位计算结果是否有进位，在两位数加法中进位只有1
            tail.next = new ListNode(1);
            tail = tail.next;
        }

        return head;
    }

    public static void main(String[] args) {
        int []arr1 = new int[]{2,4,3};
        int []arr2 = new int[]{5,6,4};
        ListNode l1 = arrToListNode(arr1);
        ListNode l2 = arrToListNode(arr2);
        ListNode listNode = new TwoNumAdd().addTwoNumbers(l1, l2);
        ArrayList<Integer> arr = new ArrayList<>();
        listNodeToArr(listNode,arr);
        System.out.println(arr);

    }

    //把数组封装成ListNode
    public static ListNode arrToListNode(int []arr){
        ListNode head = null,tail = null;
        for (int i : arr) {
            if(head == null){
                head = tail = new ListNode(i);
            }else {
                tail.next = new ListNode(i);
                tail = tail.next;
            }
        }
        return head;
    }

    //递归把ListNode转换为数组
    public static void listNodeToArr(ListNode listNode, ArrayList al){
        if(listNode.next!=null){
            al.add(listNode.val);
            listNode = listNode.next;
            listNodeToArr(listNode,al);
        }
        else{
            al.add(listNode.val);
        }
    }
}